home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / lzhsourc.lzh / LZH.SRC / LHUF5.C < prev    next >
C/C++ Source or Header  |  1992-07-02  |  23KB  |  962 lines
  1. #include "lh5.h"
  2. #include <stdlib.h>
  3. #include <string.h>  /* memmove() */
  4. #ifdef __TOS__
  5.  #include "goodputc.h"
  6. #endif
  7.  
  8. /* #define _lhufs_ */
  9.  
  10. extern uchar text_buf[DICSIZ];
  11. #define buffer text_buf
  12. /* static uchar buffer[DICSIZ]; */
  13.  
  14.  
  15.  
  16. #define CRCPOLY  0xA001  /* ANSI CRC-16 */
  17.                          /* CCITT: 0x8408 */
  18. #define UPDATE_CRC(c) \
  19.     crc = crctable[(crc ^ (c)) & 0xFF] ^ (crc >> CHAR_BIT)
  20.  
  21. extern FILE *infile, *outfile;
  22. extern uint crc;
  23. ulong  origsize,compsize;
  24. #ifdef _lhufs_
  25.  uint   bitbuf;
  26.  extern uint   subbitbuf;
  27.  extern int    bitcount;
  28.  extern ulong  origsize,compsize;
  29. #else
  30.  uint          bitbuf;
  31.  uint             subbitbuf;
  32.  int              bitcount;
  33.  ulong         origsize,compsize;
  34. #endif
  35. extern uchar flg_n;
  36.  
  37. ushort crctable[UCHAR_MAX + 1];
  38. uint  subbitbuf;
  39. int   bitcount;
  40.  
  41. static void error(char *fmt, ...)
  42. {
  43.     va_list args;
  44.  
  45.     va_start(args, fmt);
  46.     putc('\n', stderr);
  47.     vfprintf(stderr, fmt, args);
  48.     putc('\n', stderr);
  49.     va_end(args);
  50.     exit(EXIT_FAILURE);
  51. }
  52.  
  53. void make_crctable(void)
  54. {
  55.     uint i, j, r;
  56.     static int crc_ready = 0;
  57.     if (crc_ready == 0) {
  58.  
  59.     for (i = 0; i <= UCHAR_MAX; i++) {
  60.         r = i;
  61.         for (j = 0; j < CHAR_BIT; j++)
  62.             if (r & 1) r = (r >> 1) ^ CRCPOLY;
  63.             else       r >>= 1;
  64.         crctable[i] = r;
  65.     }
  66.     crc_ready=1;
  67.     }
  68. }
  69.  
  70. void fillbuf(int n)  /* Shift bitbuf n bits left, read n bits */
  71. {
  72.     bitbuf <<= n;
  73.     while (n > bitcount) {
  74.         bitbuf |= subbitbuf << (n -= bitcount);
  75.         if (compsize != 0) {
  76.             compsize--;  subbitbuf = (uchar) getc(infile);
  77.         } else subbitbuf = 0;
  78.         bitcount = CHAR_BIT;
  79.     }
  80.     bitbuf |= subbitbuf >> (bitcount -= n);
  81. }
  82.  
  83.  
  84. static uint getbits(int n)
  85. {
  86.     uint x;
  87.  
  88.     x = bitbuf >> (BITBUFSIZ - n);  fillbuf(n);
  89.     return x;
  90. }
  91.  
  92. static void putbits(int n, uint x)  /* Write rightmost n bits of x */
  93. {
  94.     if (n < bitcount) {
  95.         subbitbuf |= x << (bitcount -= n);
  96.     } else {
  97.         if (compsize < origsize) {
  98.             if (putc(subbitbuf | (x >> (n -= bitcount)), outfile) == EOF) error("Unable to write");
  99.             compsize++;
  100.         } else unpackable = 1;
  101.         if (n < CHAR_BIT) {
  102.             subbitbuf = x << (bitcount = CHAR_BIT - n);
  103.         } else {
  104.             if (compsize < origsize) {
  105.                 if (putc(x >> (n - CHAR_BIT), outfile) == EOF) error("Unable to write");
  106.                 compsize++;
  107.             } else unpackable = 1;
  108.             subbitbuf = x << (bitcount = 2 * CHAR_BIT - n);
  109.         }
  110.     }
  111. }
  112.  
  113. int fread_crc(uchar *p, int n, FILE *f)
  114. {
  115.     int i;
  116.  
  117.     i = n = fread(p, 1, n, f);  origsize += n;
  118.     while (--i >= 0) UPDATE_CRC(*p++);
  119.     return n;
  120. }
  121.  
  122. static void fwrite_crc(uchar *p, int n, FILE *f)
  123. {
  124.     if (f!= NULL) if (fwrite(p, 1, n, f) < n) error("Unable to write");
  125.     while (--n >= 0) UPDATE_CRC(*p++);
  126. }
  127.  
  128. static void init_getbits(void)
  129. {
  130.     bitbuf = 0;  subbitbuf = 0;  bitcount = 0;
  131.     fillbuf(BITBUFSIZ);
  132. }
  133.  
  134. static void init_putbits(void)
  135. {
  136.     bitcount = CHAR_BIT;  subbitbuf = 0;
  137. }
  138.  
  139. /* --------------------------- End of IO.C --------------------------- */
  140.  
  141. /***********************************************************
  142.     decode.c
  143. ***********************************************************/
  144.  
  145.  
  146.  
  147. /* ----------------------Start of huf.c ------------------------------- */
  148.  
  149. /***********************************************************
  150.     huf.c -- static Huffman
  151. ***********************************************************/
  152.  
  153. #define NP (DICBIT + 1)
  154. #define NT (CODE_BIT + 3)
  155. #define PBIT 4  /* smallest integer such that (1U << PBIT) > NP */
  156. #define TBIT 5  /* smallest integer such that (1U << TBIT) > NT */
  157. #if NT > NP
  158.     #define NPT NT
  159. #else
  160.     #define NPT NP
  161. #endif
  162.  
  163. extern ushort left[2 * NC - 1], right[2 * NC - 1];
  164. extern uchar *buf, c_len[NC], pt_len[NPT];
  165. extern int   bufsiz = 0, blocksize;
  166. extern ushort c_freq[2 * NC - 1], c_table[4096], c_code[NC],
  167.               p_freq[2 * NP - 1], pt_table[256], pt_code[NPT],
  168.               t_freq[2 * NT - 1];
  169. extern ushort dad[4096];
  170. #define c_table dad
  171.  
  172. /***** encoding *****/
  173.  
  174. void count_t_freq(void)
  175. {
  176.     int i, k, n, count;
  177.  
  178.     for (i = 0; i < NT; i++) t_freq[i] = 0;
  179.     n = NC;
  180.     while (n > 0 && c_len[n - 1] == 0) n--;
  181.     i = 0;
  182.     while (i < n) {
  183.         k = c_len[i++];
  184.         if (k == 0) {
  185.             count = 1;
  186.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  187.             if (count <= 2) t_freq[0] += count;
  188.             else if (count <= 18) t_freq[1]++;
  189.             else if (count == 19) {  t_freq[0]++;  t_freq[1]++;  }
  190.             else t_freq[2]++;
  191.         } else t_freq[k + 2]++;
  192.     }
  193. }
  194.  
  195. void write_pt_len(int n, int nbit, int i_special)
  196. {
  197.     int i, k;
  198.  
  199.     while (n > 0 && pt_len[n - 1] == 0) n--;
  200.     putbits(nbit, n);
  201.     i = 0;
  202.     while (i < n) {
  203.         k = pt_len[i++];
  204.         if (k <= 6) putbits(3, k);
  205.         else putbits(k - 3, (1U << (k - 3)) - 2);
  206.         if (i == i_special) {
  207.             while (i < 6 && pt_len[i] == 0) i++;
  208.             putbits(2, (i - 3) & 3);
  209.         }
  210.     }
  211. }
  212.  
  213. void write_c_len(void)
  214. {
  215.     int i, k, n, count;
  216.  
  217.     n = NC;
  218.     while (n > 0 && c_len[n - 1] == 0) n--;
  219.     putbits(CBIT, n);
  220.     i = 0;
  221.     while (i < n) {
  222.         k = c_len[i++];
  223.         if (k == 0) {
  224.             count = 1;
  225.             while (i < n && c_len[i] == 0) {  i++;  count++;  }
  226.             if (count <= 2) {
  227.                 for (k = 0; k < count; k++)
  228.                     putbits(pt_len[0], pt_code[0]);
  229.             } else if (count <= 18) {
  230.                 putbits(pt_len[1], pt_code[1]);
  231.                 putbits(4, count - 3);
  232.             } else if (count == 19) {
  233.                 putbits(pt_len[0], pt_code[0]);
  234.                 putbits(pt_len[1], pt_code[1]);
  235.                 putbits(4, 15);
  236.             } else {
  237.                 putbits(pt_len[2], pt_code[2]);
  238.                 putbits(CBIT, count - 20);
  239.             }
  240.         } else putbits(pt_len[k + 2], pt_code[k + 2]);
  241.     }
  242. }
  243.  
  244. void encode_c(int c)
  245. {
  246.     putbits(c_len[c], c_code[c]);
  247. }
  248.  
  249. void encode_p(uint p)
  250. {
  251.     uint c, q;
  252.  
  253.     c = 0;  q = p;  while (q) {  q >>= 1;  c++;  }
  254.     putbits(pt_len[c], pt_code[c]);
  255.     if (c > 1) putbits(c - 1, p & (0xFFFFU >> (17 - c)));
  256. }
  257.  
  258. void send_block(void)
  259. {
  260.     uint i, k, flags, root, pos, size;
  261.  
  262.     root = make_tree(NC, c_freq, c_len, c_code);
  263.     size = c_freq[root];  putbits(16, size);
  264.     if (root >= NC) {
  265.         count_t_freq();
  266.         root = make_tree(NT, t_freq, pt_len, pt_code);
  267.         if (root >= NT) {
  268.             write_pt_len(NT, TBIT, 3);
  269.         } else {
  270.             putbits(TBIT, 0);  putbits(TBIT, root);
  271.         }
  272.         write_c_len();
  273.     } else {
  274.         putbits(TBIT, 0);  putbits(TBIT, 0);
  275.         putbits(CBIT, 0);  putbits(CBIT, root);
  276.     }
  277.     root = make_tree(NP, p_freq, pt_len, pt_code);
  278.     if (root >= NP) {
  279.         write_pt_len(NP, PBIT, -1);
  280.     } else {
  281.         putbits(PBIT, 0);  putbits(PBIT, root);
  282.     }
  283.     pos = 0;
  284.     for (i = 0; i < size; i++) {
  285.         if (i % CHAR_BIT == 0) flags = buf[pos++];  else flags <<= 1;
  286.         if (flags & (1U << (CHAR_BIT - 1))) {
  287.             encode_c(buf[pos++] + (1U << CHAR_BIT));
  288.             k = buf[pos++] << CHAR_BIT;  k += buf[pos++];
  289.             encode_p(k);
  290.         } else encode_c(buf[pos++]);
  291.         if (unpackable) return;
  292.     }
  293.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  294.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  295. }
  296. uint output_pos, output_mask;
  297.  
  298. #ifdef _lhufs_
  299. extern void output5(uint c, uint p);
  300. #else
  301. void output5(uint c, uint p)
  302. {
  303.     static uint cpos;
  304.  
  305.     if ((output_mask >>= 1) == 0) {
  306.         output_mask = 1U << (CHAR_BIT - 1);
  307.         if (output_pos >= bufsiz - 3 * CHAR_BIT) {
  308.             send_block();
  309.             if (unpackable) return;
  310.             output_pos = 0;
  311.         }
  312.         cpos = output_pos++;  buf[cpos] = 0;
  313.     }
  314.     buf[output_pos++] = (uchar) c;  c_freq[c]++;
  315.     if (c >= (1U << CHAR_BIT)) {
  316.         buf[cpos] |= output_mask;
  317.         buf[output_pos++] = (uchar)(p >> CHAR_BIT);
  318.         buf[output_pos++] = (uchar) p;
  319.         c = 0;  while (p) {  p >>= 1;  c++;  }
  320.         p_freq[c]++;
  321.     }
  322. }
  323. #endif
  324. void start_huf(void)
  325. {
  326.     int i;
  327.  
  328.     if (bufsiz == 0) {
  329.         bufsiz = 16 * 1024U;
  330.         while ((buf = malloc(bufsiz)) == NULL) {
  331.             bufsiz = (bufsiz / 10U) * 9U;
  332.             if (bufsiz < 4 * 1024U) error("Out of memory.");
  333.         }
  334.     }
  335.     buf[0] = 0;
  336.     for (i = 0; i < NC; i++) c_freq[i] = 0;
  337.     for (i = 0; i < NP; i++) p_freq[i] = 0;
  338.     output_pos = output_mask = 0;
  339.     init_putbits();
  340. }
  341.  
  342. void end_huf(void)
  343. {
  344.     if (! unpackable) {
  345.         send_block();
  346.         putbits(CHAR_BIT - 1, 0);  /* flush remaining bits */
  347.     }
  348. }
  349.  
  350. /***** decoding *****/
  351.  
  352. static void read_pt_len(int nn, int nbit, int i_special)
  353. {
  354.     int i, c, n;
  355.     uint mask;
  356.  
  357.     n = getbits(nbit);
  358.     if (n == 0) {
  359.         c = getbits(nbit);
  360.         for (i = 0; i < nn; i++) pt_len[i] = 0;
  361.         for (i = 0; i <